package com.example.demo.algorithms;

import lombok.extern.slf4j.Slf4j;

/**
 * <p>Description: 背包问题</p>
 *
 * @author Eric Lee
 * @version v1.0.0
 * @since 2021/4/10 17:17
 **/
@Slf4j
public class Knapsack {

    public static void main(String[] args) {
        int[] price = {0, 2, 4, 3, 7};   //首例填充0 ，第0个物品，保持索引完整
        int[] weight = {0, 2, 3, 5, 5};  //首例填充0 ，第0个物品，保持索引完整
        int n = 4;
        int bagWeight = 10;
        int result = ks3(price, weight, n, bagWeight);
        System.out.println(result);

    }

    /**
     * @param p         价值
     * @param s         重量大小
     * @param n         n个物品
     * @param bagWeight 背包大小
     * @return
     */
    private static int ks3(int[] p, int[] s, int n, int bagWeight) {
        Integer[][] result = new Integer[n + 1][bagWeight + 1];
        // 初始化
        for (int m = 0; m <= bagWeight; m++) {
            result[0][m] = 1;
        }
        for (int m = 0; m <= n; m++) {
            result[m][0] = 0;
        }
        // 开始填表
        for (int i = 1; i <= n; i++) {                // 第i个物品
            for (int iWeight = 1; iWeight <= bagWeight; iWeight++) {     // 该物品重量
                System.out.print("" + i + "物品");
                System.out.print(",重量：" + s[i]);
                System.out.print(",价值：" + p[i]);
                System.out.println(" ----- 背包容量" + iWeight);
                if (iWeight < s[i]) {
                    // 装不进去
                    System.out.println(String.format("背包容量%s >= 物品%s的重量%s ---装不进去", iWeight, i, s[i]));
                    result[i][iWeight] = result[i - 1][iWeight];
                    System.out.print(String.format("装进去的总价值%s", result[i][iWeight]));
                } else {
                    // 容量足够
                    if (result[i - 1][iWeight] > result[i - 1][iWeight - s[i]] + p[i]) {
                        // 不装该珠宝，最优价值更大
                        System.out.println(String.format("背包容量%s >= 物品%s的重量%s ---不装进去最优", iWeight, i, s[i]));
                        result[i][iWeight] = result[i - 1][iWeight];
                        System.out.print(String.format("装进去的总价值%s", result[i][iWeight]));
                    } else {
                        System.out.println(String.format("背包容量%s >= 物品%s的重量%s ---装进去最优", iWeight, i, s[i]));
                        result[i][iWeight] = result[i - 1][iWeight - s[i]] + p[i];
                        System.out.print(String.format("装进去的总价值%s", result[i][iWeight]));
                    }
                }
                System.out.println(" \n");
            }
        }
        return result[n][bagWeight];
    }
}
